A Burrows Wheeler Transform Implementation
This is a simple, inefficient implementation of the Burrows-Wheeler transform in C++. I wrote it just to play around with the algorithm, not for any practical application. It takes a single text file as the input, then performs the transform and reverses it:
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
void bwt(string input,string &bwt_str,int &primaryidx) {
vector<string> rotations;
// 1. generate rotations of input
cout << "rotations:" << endl;
for(int n=0;n<input.size();n++) {
string s;
s += input[n];
for(int i=n+1;i!=n;i++) {
if(i==input.size()) i=0;
s += input[i];
if(i==input.size()-1) i=-1;
}
rotations.push_back(s);
cout << s << endl;
}
// 2. sort
cout << "sorted:" << endl;
sort(rotations.begin(),rotations.end());
for(size_t n=0;n<rotations.size();n++) {
cout << rotations[n] << endl;
}
bwt_str.clear();
for(size_t n=0;n<rotations.size();n++) {
bwt_str += rotations[n].substr(rotations[n].size()-1,1);
if(rotations[n] == input) {primaryidx = n;}
}
cout << "bwt string: " << bwt_str << endl;
cout << "primaryidx: " << primaryidx << endl;
}
string rbwt(string bwt_str,int primaryidx) {
vector<string> cur_str;
for(size_t n=0;n<bwt_str.size();n++) {
string s;
s = bwt_str.substr(n,1);
cur_str.push_back(s);
}
for(;cur_str[0].size() < bwt_str.size();) {
vector<string> new_str = cur_str;
sort(new_str.begin(),new_str.end());
for(size_t n=0;n<cur_str.size();n++) {
cur_str[n] = cur_str[n] + new_str[n].substr(new_str[n].size()-1,1);
}
}
cout << "reversed transform:" << endl;
for(size_t n=0;n<cur_str.size();n++) {
cout << cur_str[n] << endl;
}
sort(cur_str.begin(),cur_str.end());
cout << "Original String: " << cur_str[primaryidx] << endl;
return cur_str[primaryidx];
}
int main(int argc,char **argv) {
string s;
ifstream infile(argv[1]);
for(;!infile.eof();) {
char c = (char)infile.get();
if(!infile.eof()) s += string(1,c);
}
cout << "input: " << s << "END" << endl;
string bwt_str;
int primaryidx;
bwt(s,bwt_str,primaryidx);
rbwt(bwt_str,primaryidx);
}
RSS